Debugging is a process of finding and correcting errors (“bugs”) in a computer program, in order to make the computer program behave as expected. Debugging may require efforts and significant time from a programmer. It may be particularly difficult to find concurrent bugs, for example, unintentional race conditions or deadlocks, which may exist in multi-threaded computer programs.
A “delta debugging” algorithm may be used for locating some bugs. The algorithm receives a set of program changes that appear to induce a bug, and searches for a minimal subset of the program that still induces the bug. A delta debugging algorithm assumes that the bug is monotonic, namely, exists in all supersets of the received set of program changes; unfortunately, this assumption may not hold true for many concurrent bugs.
A “tarantula” fault-localization technique computes rankings of code statements, based on their likelihood (“suspiciousness”) to contribute to failed runs of the computer program. Unfortunately, this technique, which analyzes code at a statement level, may not find bugs associated with the concurrent domain. Furthermore, the programmer is required to independently (e.g., manually) sample the program in order to apply this technique.
Similarly, a “GeneticFinder” debugging algorithm analyzes code at a statement level, and may not find bugs associated with the concurrent domain. Furthermore, this algorithm uses extensive (e.g., complete) instrumentation of the program, which in turn may change the scheduling of one or more program portions and may thus further reduce the probability of finding concurrent bugs.
A statistical debugging method may be used to identify probable bug locations in single-thread programs. Unfortunately, this method includes instrumentation by manual insertion of assertions into program code, and this may be effort-consuming and time-consuming, particularly in large programs. Additionally, a significant number of program runs, and/or a diverse sample of programs runs, may be required in order to execute all the placed assertions. Furthermore, this debugging method may require manual tuning of parameters of a classifier which attempts to predict the outcome of program runs (namely, success or failure) based on the outcomes of the assertions.
A runtime algorithm, for example, a race detector, may be used to identify probable bug locations. Unfortunately, the runtime algorithm may generate numerous “false alarms”; and may require extensive (e.g., complete) instrumentation of the program, which in turn may change the scheduling of one or more program portions and may thus further reduce the probability of finding concurrent bugs.